#include <stdlib.h>
#include <stdio.h>

typedef char DataType;
#define ok 0
#define ERROR 1
typedef struct Node
{
    DataType data;/*数据域*/
    struct Node *leftChild;/*左子树指针*/
    struct Node *rightChild;/*右子树指针*/
} BiTreeNode;/*结点的结构体定义*/

// 根据带有显式空子节点的先序序列，构建二叉树，将其根节点的地址存入 *root_pp 中
// 初始传入的root_pp的值无任何意义（也即root_pp尚未被正确地初始化，因此需要你来初始化）
// pre_order_seq 指向的字符串类似 "ABC##DE#G##F###"，其中 # 表示显式的空子节点（空指针域），
// 这一类空子节点并不需要被创建对应的struct Node或者BiTreeNode
int _create_tree(BiTreeNode **root_pp,char * pre_order_seq,int *current_index){
    int status_sub_tree;

    if(pre_order_seq[*current_index] == '\0'){
        //TODO
        (*root_pp) = NULL;
        return ok;
    }
    if(pre_order_seq[*current_index] == '#'){
        *root_pp = NULL;
        //需要消耗掉这个#字符，因此*current-indez 需要+1
        *current_index += 1;
        return ok;
    }
    (*root_pp)= (BiTreeNode*)malloc(sizeof(BiTreeNode));
    if(!(*root_pp)){
        printf("failed to allocate memory,now exit()");
        return ERROR;
    }
    (*root_pp)->data = pre_order_seq[*current_index];
    *current_index += 1;
    status_sub_tree = _create_tree(&((*root_pp)->leftChild),pre_order_seq, current_index);
    if(status_sub_tree == ERROR){
        return status_sub_tree;
    }
    status_sub_tree = _create_tree(&((*root_pp))->rightChild,pre_order_seq,current_index);
    if(status_sub_tree == ERROR){
        return status_sub_tree;
    }
    return ok;
}
void create_tree(BiTreeNode ** root_pp, char * pre_order_seq,int num_elements) {
    int num_scanned_chars=0;
    _create_tree(root_pp, pre_order_seq,&num_scanned_chars);
    num_elements = num_scanned_chars;
    //	num_scanned_chars num_elements
}

//使用visit(item)函数前序遍历二叉树t
void pre_order_traverse(BiTreeNode *t, void visit(DataType item))
{
    if(t == NULL){
        return;
    }
    visit(t->data);
    pre_order_traverse(t->leftChild,visit);
    pre_order_traverse(t->rightChild,visit);
}

//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode *t, void visit(DataType item))
{
    if(t == NULL){
        return;
    }

    in_order_traverse(t->leftChild,visit);
    visit(t->data);
    in_order_traverse(t->rightChild,visit);
}

//使用void visit(DateType item)函数后序遍历二叉树t
void post_order_traverse(BiTreeNode *t, void visit(DataType item))
{
    if(t == NULL){
        return;
    }

    post_order_traverse(t->leftChild,visit);

    post_order_traverse(t->rightChild,visit);
    visit(t->data);
}

// 可以无需更改本函数的实现
void visit(DataType item)
{
    printf("%c ", item);
}

// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode * search(BiTreeNode *root, DataType x)//我这里把find设置为null所以一直为空指针！！！
{
    BiTreeNode *find=NULL;
    find = root;

    if(find == NULL){
        return find;
    }
    if(find->data == x){
        return find;
    }
    if(search(find->leftChild,x)){
        find=search(find->leftChild,x);
        return find;
    }
    if(search(find->rightChild,x)){
        find=search(find->rightChild,x);
        return find;
    }
    return NULL;
}

// 递归地销毁由 *root 所指向根节点的树：释放该树涉及的所有动态分配的内存空间
void destroy(BiTreeNode **root)
{
    if(root != NULL){
        if((*root)->leftChild != NULL){
            destroy(&(*root)->leftChild);
        }
        if((*root)->rightChild!= NULL){
            destroy(&(*root)->leftChild);
        }
        root = NULL;
    }
}
int main(){
    char *a=NULL;
    char s[]="ABC##DE#G##F###";
    int count=0;
    BiTreeNode *root=NULL;
    BiTreeNode *find=NULL;
    a = s;
    /*while(*a){
printf("%c",*a);
a++;
}*/
    create_tree(&root,a,count);
    //_create_tree(&root,a,&count);
    //pre_order_traverse(root,visit);
    //in_order_traverse(root,visit);
    //post_order_traverse(root,visit);
    find=search(root,'F');
    if(find == NULL){
        printf("无元素");
    }else{
        printf("%c",(find->data));
    }
    destroy(&root);


    //printf("%c",(root->data));
    system("pause");
}
/*
pre_order_seq这个东西没有被引用到！！！
*/
